package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;


/**
 * 3-opt
 */
public class Ls3opt extends LocalSearch {


    public Ls3opt(Problem problem) {
        super(problem);
    }

    @Override
    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search 3opt init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search 3opt final", finalSolution);
        CheckUtils.check(finalSolution, distance);
    }


    @Override
    protected Solution improve(Solution solution) {
        int n = solution.length();
        Solution currentSolution = solution.copy();

        for (int i = 0; i < n - 5; i++) {
            for (int j = i + 2; j < n - 3; j++) {
                for (int k = j + 2; k < n - 1; k++) {
                    List<Integer> currPath = currentSolution.getPermutation();
                    int currCost = currentSolution.getCost();
                    List<List<Integer>> newPaths = makeMove(currPath, i, j, k);
                    for (List<Integer> path : newPaths) {
                        int cost = calculateFitness(path);
                        if (cost < currCost) {
                            currPath = path;
                            currCost = cost;
                        }
                    }
                    if (currCost < currentSolution.getCost()) {
                        currentSolution = new Solution(currPath, currCost);
                    }
                }
            }
        }

        return currentSolution;
    }


    private List<List<Integer>> makeMove(List<Integer> permutation, int i, int j, int k) {

        List<Integer> A = new ArrayList<>(permutation.subList(0, j + 1));
        List<Integer> B = new ArrayList<>(permutation.subList(j + 1, k + 1));
        List<Integer> C = new ArrayList<>(permutation.subList(k + 1, permutation.size()));
        List<Integer> a = new ArrayList<>(permutation.subList(0, i + 1));
        a.addAll(reverse(permutation.subList(i + 1, j + 1)));
        List<Integer> b = reverse(B);
        List<Integer> c = reverse(C);

        // 7 kind of variants
        List<List<Integer>> res = new ArrayList<>();
        // 1
        res.add(merge(a, B, C));
        res.add(merge(A, b, C));
        res.add(merge(A, B, c));
        // 2
        res.add(merge(A, b, c));
        res.add(merge(a, b, C));
        res.add(merge(a, B, c));
        // 3
        res.add(merge(a, b, c));

        return res;
    }

    private List<Integer> merge(List<Integer> a, List<Integer> b, List<Integer> c) {
        List<Integer> s = new ArrayList<>();
        s.addAll(a);
        s.addAll(b);
        s.addAll(c);
        return s;
    }

    private List<Integer> reverse(List<Integer> s) {
        List<Integer> r = new ArrayList<>();
        for (int i = 0; i < s.size(); i++) {
            r.add(s.get(s.size() - 1 - i));
        }
        return r;
    }

}
